package one.three.ten;

public class InfixToPostfix {

	static class Node {
		private String item;
		private Node next;
		private Node previous;

		public Node(String item, Node next, Node previous) {
			this.item = item;
			this.next = next;
			this.previous = previous;
		}

		@Override
		public String toString() {
			Node node = this;
			StringBuilder s = new StringBuilder();
			while (node != null) {
				s.append("[ " + node.item + " ]");
				node = node.next;
			}
			return s.toString();
		}
	}

	public static boolean noParentheses(Node node) {
		while (node != null) {
			if (node.item.equals("(") || node.item.equals(")"))
				return false;
			node = node.next;
		}
		return true;
	}

	public static String infixToPostfix(String[] a) {
		Node first = new Node(a[0], null, null);
		Node cur = first;
		Node n;
		for (int i = 1; i < a.length; i++) {
			n = new Node(a[i], null, cur);
			cur.next = n;
			cur = n;
		}

		while (!noParentheses(first)) {
			Node node = first;
			Node p;
			while (node != null) {
				if (node.item.equals(")")) {
					String e2 = node.previous.item;
					String o = node.previous.previous.item;
					String e1 = node.previous.previous.previous.item;
					p = node.previous.previous.previous.previous;
					Node newNode = new Node(e1 + " " + e2 + " " + o, node.next, p.previous != null ? p.previous : null);
					node.next.previous = newNode;
					if (p.previous != null) {
						p.previous.next = newNode;
					} else {
						first = newNode;
					}
				}
				node = node.next;
			}
		}

		Node node = first;
		Node p;
		while (node != null) {
			if (node.item.equals("*") || node.item.equals("/")) {
				String e1 = node.previous.item;
				String o = node.item;
				String e2 = node.next.item;
				p = node.previous.previous;
				Node newNode = new Node(e1 + " " + e2 + " " + o, node.next.next, p != null ? p : null);
				if (p != null) {
					p.next = newNode;
				} else {
					first = newNode;
				}
				if (node.next.next != null) {
					node.next.next.previous = newNode;
				}
			}
			node = node.next;
		}

		node = first;
		while (node != null) {
			if (node.item.equals("+") || node.item.equals("-")) {
				String e1 = node.previous.item;
				String o = node.item;
				String e2 = node.next.item;
				p = node.previous.previous;
				Node newNode = new Node(e1 + " " + e2 + " " + o, node.next.next, p != null ? p : null);
				if (p != null) {
					p.next = newNode;
				} else {
					first = newNode;
				}
				if (node.next.next != null) {
					node.next.next.previous = newNode;
				}
			}
			node = node.next;
		}
		return first.item;
	}

	// (1 + 4) * 3 + 10 / 5
	// 3 1 4 + * 10 5 / +
	public static void main(String[] args) {
		 String[] a = { "(", "1", "+", "4", ")", "*", "3", "+", "10", "/", "5" };
		//String[] a = { "(", "1", "+", "(", "3", "+", "5", ")", ")", "*", "3", "+", "10", "/", "5" };
		String r=infixToPostfix(a);
		System.out.println(r);
	}

}
